﻿using System;

namespace HeapSort
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			Console.WriteLine (" Heap Sort ! ");
			int[] array = new int[]{0,76,50,65,49,97,15,38,27};
			heapsort (array,8);
			foreach (int item in array) {
				System.Console.WriteLine (item+" ");
			}
		}

		static void sift(int[] arr,int k,int m)
		{
			int i, j;
			int temp;
			i = k;temp = arr [i];j = 2 * i;
			while (j <= m) 
			{
				if (j < m && arr [j] > arr [j + 1])
					j++;
				if (temp > arr [j]) {
					arr [i] = arr [j];
					i = j;
					j *= 2;
				} else
					break;
			}
			arr [i] = temp;
		}

		static void heapsort(int[] arr,int n)
		{
			int temp;
			for (int i = n; i >= 1; i--) {
				sift (arr, i, n);
			}
			for (int i = n; i >= 2; i--) {
				temp = arr [1];
				arr [1] = arr [i];
				arr [i] = temp;
				sift (arr,1,i-1);
			}
		}
	}
}
